#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2021-01-11 9:16 上午
# @Author  : yangdy
# @File    : 2021-01-11.1202.交换字符串中的元素
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        # 1.union
        # fathers = [i for i in range(len(s))]
        #
        # def cut(x):
        #     if fathers[x] == x:
        #         return x
        #     fathers[x] = cut(fathers[x])
        #     return fathers[x]
        #
        # def union(x, y):
        #
        #     fathers[cut(x)] = cut(y)
        #
        # for pi in pairs:
        #     union(pi[0], pi[1])
        # cc = [[] for i in range(len(s))]
        # for i in range(len(s)):
        #     cc[cut(i)].append(i)
        # ans = list(s)
        # for ci in cc:
        #     a = sorted(ci)
        #     b = sorted(ans[i] for i in ci)
        #     for i in range(len(a)):
        #         ans[a[i]] = b[i]
        #
        # return ''.join(ans)
        mm = [[] for i in range(len(s))]
        for pi in pairs:
            mm[pi[0]].append(pi[1])
            mm[pi[1]].append(pi[0])

        def dfs(x, state, res, graph):
            if state[x] != 0:
                return
            state[x] = 1
            res.append(x)
            for y in graph[x]:
                dfs(y, state, res, graph)
            state[x] = 2

        def bfs(x, state, res, graph):
            if state[x] != 0:
                return
            state[x] = 1
            que, i = [x], 0
            res.append(x)
            while i < len(que):
                for y in graph[que[i]]:
                    if state[y] == 0:
                        state[y] = 1
                        res.append(y)
                        que.append(y)
                i += 1

        ans = list(s)
        ss = [0 for i in range(len(s))]
        for i in range(len(s)):
            if ss[i] == 0:
                nodes = []
                # dfs(i, ss, nodes, mm)
                bfs(i, ss, nodes, mm)
                print(nodes)
                a = sorted(nodes)
                b = sorted(ans[i] for i in nodes)
                for j in range(len(a)):
                    ans[a[j]] = b[j]
        return ''.join(ans)


questions = [
    ("dcab", [[0, 3], [1, 2]]),
    ("dcab", [[0, 3], [1, 2], [0, 2]]),
    ("cba", [[0, 1], [1, 2]]),
    ("udyyek", [[3, 3], [3, 0], [5, 1], [3, 1], [3, 4], [3, 5]])
]

work(questions, lambda q: Solution().smallestStringWithSwaps(q[0], q[1]))
